1. Field of the Invention
The present invention relates to computer networks. In particular, the present invention relates to providing a reliable multicast service without requiring the sender to check successful receipt of the multicast packet by each individual recipient.
2. Discussion of the Related Art
3GPP, 3GPP2 and WLAN systems provide multicasting services, i.e., each system is capable of distributing information from a source to multiple receivers in a multicast area using a single broadcast. Multicasting allows efficient use of scarce network resources (e.g., the air interface) when sending the same information to multiple users.
In applications such as multimedia streaming and location-based advertising, receivers in a multicast group can tolerate some packet losses. In such applications, to keep the system simple, unreliable multicast services without loss recovery ability may be used. To maintain acceptable performance, the application can use upper layer reliable mechanisms (e.g., application layer forward error coding) to decrease packet loss percentage. However, for an application that is “non-fault-tolerant” (e.g., software upgrade distribution, distributed computing or network management which require “non fault-tolerant” information), or an application which can only tolerate a very small percentage of the transmitted packets to be lost, a reliable multicast services is desired due to the fast recovery requirement.
IP and link layer protocols are the two main existing categories of reliable multicast. IP-layer multicast protocols focus on end-to-end multicast between heterogeneous senders and receivers interconnected through the Internet. Link layer multicast protocols focus on multicast support between adjacent senders and receivers interconnected by a common multi-access shared link. Until now, more research has been devoted to IP layer multicast protocols than link layer multicast protocols.
Current link layer multicast protocols are applicable only to local area networks that has a small bandwidth-delay product and which uses stop-and-wait automatic repeat request (ARQ) mechanism to recover packet loss (e.g., 802.11 type of WLAN). Such multicast protocols are not scalable for a wireless network with a large bandwidth-delay product. Thus, there is a need for a reliable multicast protocol for a wireless network with a large bandwidth-delay product.
A reliable multicast protocol must overcome the “feedback implosion problem” that arises as a result of the number of receivers. The feedback implosion problem is illustrated by FIG. 1. As shown in FIG. 1, if each multicast packet sent from a single source S1 requires an acknowledgement from each of recipients R1-R5, the number of acknowledgement (positive or negative) packets increases as the number of receivers. Thus, acknowledgement packets from a large number of multicast receivers can overwhelm the sender's processing capacity, and also cause congestion in the sender's neighboring routers and local networks.
Sender-initiated protocols are typically vulnerable to the feedback implosion problem, as these protocols require the sender to be responsible for reliable delivery. In such a protocol, the sender keeps tracks of the acknowledgement packets received from the receivers. Further aggravating the problem are the requirements that (1) all transmissions and retransmissions (i.e., recovery transmissions) are multicast to all receivers, and (2) the sender continues to track the changing set of active receivers and their reception states. In particular, because the IP multicast model requires a multicast data packet to be addressed to a multicast group—thereby imposing a level of indirection between the sender and the receivers—it may be expensive or impossible for the sender to track the reception state of each receiver.
To circumvent the problems inherent with sender-initiated protocols, most scalable and reliable multicast protocols are receiver-initiated protocols, which require each receiver to be responsible for reliable packet delivery to itself. In such a protocol, a receiver sends a negative feedback or negative acknowledgement packet (i.e., NACK packet) to the sender when a retransmission is required (e.g., when an error is detected, a packet of an expected sequence number is not received, or a timeout occurs), and the sender is not required to maintain an updated receiver list. As compared to a sender-initiated protocol, a receiver-initiated protocol is generally less sensitive to the number of receivers receiving the multicast and results in a substantially lesser number of feedback packets. Receiver-initiated protocols are thus more scalable than sender-initiated protocols. Nevertheless, receiver-initiated protocols are still vulnerable to a NACK-implosion at the sender, when transmission errors are widespread at any given time, thereby resulting in a large number of NACK packets at the same time. Such a condition may occur when a resource is shared in a multicast tree, so that correlated losses among different receivers can occur. For example, when a packet is lost on a link to a sub-tree, each receiver downstream from the link will experience a loss and will then respond with negative feedback at substantially the same time.
The NACK implosion problem may be overcome by “timer-based protocols”, which assign different delays to the receivers. Under such a protocol, upon detecting a packet loss, rather than sending a NACK immediately, a receiver waits until its assigned delay expires before sending the NACK packet. Timer-based protocols thus stagger NACK packets from different receivers. Ideally, one of the receivers sends out a NACK packet early enough in time to allow the retransmission to occur before other receivers send their NACK packets. Alternatively, if the NACK packet is multicast to all receivers, other receivers may refrain from sending their own NACK packets in anticipation of the retransmission responsive to the first NACK packet. The performance of timer-based protocols thus depends on the algorithm that assigns timeout values to the different receivers.
To provide scalable reliable multicast services, “structure-based protocols” distribute the NACK (or ACK) processing tasks to multiple nodes, so that the sender's load can be decreased. These protocols organize multicast receivers into different logical network structures such as a tree. In such an organization, a downstream node sends its ACK or NACK packets upstream to an intermediate node between it and the sender. The downstream node also receives recovery packets from the intermediate node. When the intermediate node is unable to provide recovery, the NACK or ACK packet is passed further upstream to the sender node.
An important aspect of a reliable multicast protocol is error recovery. While most reliable multicast protocols use a pure ARQ scheme to recover a packet loss, a hybrid forward error correction (FEC) and ARQ scheme may substantially reduce feedback implosion and the expected delay of packet delivery without an increased bandwidth requirement. In the prior art, there are two kinds of hybrid FEC and ARQ schemes. In a first kind, repair bits are sent within a repair packet to correct bit errors or erasures, unless the number of repair bits is large. In that case, a retransmission scheme is used. In a second kind, the repair bits are transmitted separately from the data packets.
The protocols discussed above all operate in the IP layer. A link layer protocol extends reliable multicast in multi-access wireless LANs at the last hop of a wireless link, using both positive feedback (ACK) and negative feedback (NACK) packets. Under this protocol, a receiver in the multicast group is chosen as a “leader” or representative for the purpose of sending feedback to the sender (e.g., a base station). Whenever the leader successfully receives a packet, it returns an ACK packet. However, if this leader node detects an error in the received data packet, the leader node does not send an acknowledgement, thereby triggering an automatic retransmission from the sender. If another receiver, not the leader, detects an error in its received packet, this receiver sends out a negative acknowledgement (NACK) packet, which conflicts with the ACK packet sent from the leader. When such a condition occurs, the sender retransmits the packet.
IP layer multicast protocols typically include techniques for maintaining the multicast tree, estimating round-trip-time delay, managing group membership, and choosing error recovery methods. These protocols are designed for complex network topologies in which senders and receivers are interconnected with multi-hop links and have different link bandwidths, crossover traffic, and loss probabilities. For a simple topology involving one sender and multiple receivers connected by single shared wireless link, using such an IP layer multicast would be inefficient and overkill.
The article “Parity-based loss recovery for reliable multicast transmission,” by J. Nonnenmacher, E. Biersack, and D. Towsley, IEEE Tran. on Networking, August 1998 describes a multicast scheme that (1) uses a stop-and-wait ARQ scheme to recover packet loss, (2) selects a single receiver as a leader of the multicast group, and (3) treats a collision of an ACK packet and a NACK packet as a negative acknowledgement. However, this stop-and-wait ARQ scheme is suitable only for a 802.11 type network having a small bandwidth-delay product. For a wireless network with a high bandwidth-delay product (e.g., a 802.20 network), a stop-and-wait ARQ scheme is considered wasteful of channel bandwidth. Also, the single leader approach represents a single point of potential failure and requires some overhead for leader maintenance. Further, the NACK and ACK collision approach can be used only in system where, at any given time, only one packet is outstanding and remains to be acknowledged. Under such a scheme, the sender determines an unsuccessful transmission by detecting collision, without having to examine the details of the acknowledgement received. However, if multiple packets can remain unacknowledged, the sender needs to examine each acknowledgement to find out which packets among the outstanding ones are lost. So the collision of ACK and NACK packets only signals the loss of some packet, unless further examination is carried out.